﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using log4net.Repository.Hierarchy;
using log4net;
using TsTreeTimeSeries.node;

namespace TsTreeTimeSeries.tstree
{
   class TSTree
    {
        #region Variables
        public int maxNodeEntries;
        public int minNodeEntries;
        // initialisation
        private int treeHeight = 1; // leaves are always level 1
        private int rootNodeId = 0;
        private int msize = 0;

        //private TIntObjectHashMap nodeMap = new TIntObjectHashMap();
        private Dictionary<int, Node> nodeMap = new Dictionary<int, Node>();
        //private TIntStack parents = new TIntStack();
        private Stack<int> parents = new Stack<int>();
        //private TIntStack parentsEntry = new TIntStack();
        private Stack<int> parentsEntry = new Stack<int>();
        private int highestUsedNodeId = 0;

        // Deleted Node&lt;T&gt; objects are retained in the nodeMap,
        private Stack<int> deletedNodeIds = new Stack<int>();
        // used to mark the status of entries during a Node&lt;T&gt; split
        private const int ENTRY_STATUS_ASSIGNED = 0;
        private const int ENTRY_STATUS_UNASSIGNED = 1;
        private byte[] entryStatus = null;
        private byte[] initialEntryStatus = null;
        // internal consistency checking - set to true if debugging tree corruption
        private const bool INTERNAL_CONSISTENCY_CHECKING = false;

        private const int DEFAULT_MAX_NODE_ENTRIES = 3;

        #endregion
        #region GET SET

        public Dictionary<int, Node> NodeMap
        {
            get { return nodeMap; }
            set { nodeMap = value; }
        }
        public int RootNodeId
        {
            get { return rootNodeId; }
            set { rootNodeId = value; }
        }
        public int Height
        {
            get { return treeHeight; }
            set { treeHeight = value; }
        }

        public Stack<int> ParentsList
        {
            get { return parents; }
            set { parents = value; }
        }

        public Stack<int> ParentsEntryList
        {
            get { return parentsEntry; }
            set { parentsEntry = value; }
        }
        #endregion
        #region Constructor
        public TSTree()
        {
            init();
        }

        public TSTree(int MaxNodeEntries, int MinNodeEntries)
        {
            minNodeEntries = MinNodeEntries;
            maxNodeEntries = MaxNodeEntries;
            init();
        }

        private void init()
        {
            // Obviously a Node&lt;T&gt; with less than 2 entries cannot be split.
            // The Node&lt;T&gt; splitting algorithm will work with only 2 entries
            // per node, but will be inefficient.
            if (maxNodeEntries < 2)
            {
                System.Console.WriteLine("Invalid MaxNodeEntries = " + maxNodeEntries + " Resetting to default value of " + DEFAULT_MAX_NODE_ENTRIES);
                maxNodeEntries = DEFAULT_MAX_NODE_ENTRIES;
            }

            // The MinNodeEntries must be less than or equal to (int) (MaxNodeEntries / 2)
            if (minNodeEntries < 1 || minNodeEntries > maxNodeEntries / 2)
            {
                System.Console.WriteLine("MinNodeEntries must be between 1 and MaxNodeEntries / 2");
                minNodeEntries = maxNodeEntries / 2;
            }

            entryStatus = new byte[maxNodeEntries];
            initialEntryStatus = new byte[maxNodeEntries];

            for (int i = 0; i < maxNodeEntries; i++)
            {
                initialEntryStatus[i] = ENTRY_STATUS_UNASSIGNED;
            }

            Node root = new Node(rootNodeId, 1, maxNodeEntries);
            nodeMap.Add(rootNodeId, root);

            System.Console.WriteLine("init() " + " MaxNodeEntries = " + maxNodeEntries + ", MinNodeEntries = " + minNodeEntries);
        }
        #endregion

        #region InsertEntry
        // chen phan tu moi
        public bool InsertEntry(Entry r, int id, int level)
        {
            System.Console.WriteLine("Start insert entry....");
            // I1 [Find position for new record] Invoke ChooseLeaf to select a
            Node n = chooseNode(r, level);
            //System.Console.WriteLine("so entry in node" + n.entryCount.ToString());
            Node newLeaf = null;
            // I2 [Add record to leaf node] If L has room for another entry,
            // install E. Otherwise invoke SplitNode to obtain L and LL containing
            // E and all the old entries of L
            if (n.entryCount < maxNodeEntries)
            {
                n.addEntryNoCopy(r, id);
                //System.Console.WriteLine("addEntryNoCopy ....");
            }
            else
            {
                newLeaf = splitNode(n, r, id);
                //System.Console.WriteLine("splitNode ....");
            }

            // I3 [Propagate changes upwards] Invoke AdjustTree on L, also passing LL
            // if a split was performed
            Node newNode = adjustTree(n, newLeaf);
            // System.Console.WriteLine("adjustTree ....");
            // I4 [Grow tree taller] If Node&lt;T&gt; split propagation caused the root to
            // split, create a new root whose children are the two resulting nodes.
            if (newNode != null)
            {
                int oldRootNodeId = rootNodeId;
                Node oldRoot = getNode(oldRootNodeId);

                rootNodeId = getNextNodeId();
                treeHeight++;
                Node root = new Node(rootNodeId, treeHeight, maxNodeEntries);
                root.addEntry(newNode.sumEntry, newNode.nodeId);
                root.addEntry(oldRoot.sumEntry, oldRoot.nodeId);
                nodeMap.Add(rootNodeId, root);
            }

            if (INTERNAL_CONSISTENCY_CHECKING)
            {
                checkConsistency(rootNodeId, treeHeight, null);
            }

            return true;
        }

        private void checkConsistency(int nodeId, int expectedLevel, Entry expectedMBR)
        {
            // go through the tree, and check that the internal data structures of
            // the tree are not corrupted.    
            Node n = getNode(nodeId);

            if (n == null)
            {
                System.Console.WriteLine("Error: Could not read Node<T> " + nodeId);
            }

            if (n.level != expectedLevel)
            {
                System.Console.WriteLine("Error: Node<T> " + nodeId + ", expected level " + expectedLevel + ", actual level " + n.level);
            }

            Entry calculatedMBR = calculateMBR(n);

            if (!n.sumEntry.Equals(calculatedMBR))
            {
                System.Console.WriteLine("Error: Node<T> " + nodeId + ", calculated MBR does not equal stored MBR");
            }

            if (expectedMBR != null && !n.sumEntry.Equals(expectedMBR))
            {
                System.Console.WriteLine("Error: Node<T> " + nodeId + ", expected MBR (from parent) does not equal stored MBR");
            }

            // Check for corruption where a parent entry is the same object as the child MBR
            if (expectedMBR != null && n.sumEntry.sameObject(expectedMBR))
            {
                System.Console.WriteLine("Error: Node<T> " + nodeId + " MBR using same rectangle object as parent's entry");
            }

            for (int i = 0; i < n.entryCount; i++)
            {
                if (n.entries[i] == null)
                {
                    System.Console.WriteLine("Error: Node<T> " + nodeId + ", Entry " + i + " is null");
                }

                if (n.level > 1)
                { // if not a leaf
                    checkConsistency(n.ids[i], n.level - 1, n.entries[i]);
                }
            }
        }

        private Node adjustTree(Node n, Node nn)
        {
            // AT1 [Initialize] Set N=L. If L was split previously, set NN to be
            // the resulting second node.

            // AT2 [Check if done] If N is the root, stop
            while (n.level != treeHeight)
            {

                // AT3 [Adjust covering rectangle in parent entry] Let P be the parent
                // Node<T> of N, and let En be N's entry in P. Adjust EnI so that it tightly
                // encloses all entry rectangles in N.
                Node parent = getNode(parents.Pop());
                int entry = parentsEntry.Pop();

                if (parent.ids[entry] != n.nodeId)
                {
                    System.Console.WriteLine("Error: entry " + entry + " in Node<T> " +
                         parent.nodeId + " should point to Node<T> " +
                         n.nodeId + "; actually points to Node<T> " + parent.ids[entry]);
                }

                if (!parent.entries[entry].Equals(n.sumEntry))
                {
                    parent.entries[entry].set(n.sumEntry.lowerBound, n.sumEntry.upperBound);
                    parent.sumEntry.set(parent.entries[0].lowerBound, parent.entries[0].upperBound);
                    for (int i = 1; i < parent.entryCount; i++)
                    {
                        parent.sumEntry.add(parent.entries[i]);
                    }
                }

                // AT4 [Propagate Node<T> split upward] If N has a partner NN resulting from
                // an earlier split, create a new entry Enn with Ennp pointing to NN and
                // Enni enclosing all rectangles in NN. Add Enn to P if there is room.
                // Otherwise, invoke splitNode to produce P and PP containing Enn and
                // all P's old entries.
                Node newNode = null;
                if (nn != null)
                {
                    if (parent.entryCount < maxNodeEntries)
                    {
                        parent.addEntry(nn.sumEntry, nn.nodeId);
                    }
                    else
                    {
                        newNode = splitNode(parent, nn.sumEntry.copy(), nn.nodeId);
                    }
                }

                // AT5 [Move up to next level] Set N = P and set NN = PP if a split
                // occurred. Repeat from AT2
                n = parent;
                nn = newNode;

                parent = null;
                newNode = null;
            }

            return nn;
        }
        private Node chooseNode(Entry r, int level)
        {
            // CL1 [Initialize] Set N to be the root node
            Node n = getNode(rootNodeId);
            parents.Clear();
            parentsEntry.Clear();

            // CL2 [Leaf check] If N is a leaf, return N
            while (true)
            {
                if (n == null)
                {
                    System.Console.WriteLine("Could not get root Node<T> (" + rootNodeId + ")");
                }

                if (n.level == level)
                {
                    return n;
                }

                // CL3 [Choose subtree] If N is not at the desired level, let F be the entry in N
          
                float leastEnlargement = n.getEntry(0).MinDist(r);
                int index = 0; // index of rectangle in subtree
                for (int i = 1; i < n.entryCount; i++)
                {
                    Entry tempRectangle = n.getEntry(i);
                    float tempEnlargement = tempRectangle.MinDist(r);
                    if ((tempEnlargement < leastEnlargement) ||
                        ((tempEnlargement == leastEnlargement) &&
                         (tempRectangle.area() < n.getEntry(index).area())))
                    {
                        index = i;
                        leastEnlargement = tempEnlargement;
                    }
                }

                parents.Push(n.nodeId);
                parentsEntry.Push(index);

                // CL4 [Descend until a leaf is reached] Set N to be the child Node&lt;T&gt;
                // pointed to by Fp and repeat from CL2
                n = getNode(n.ids[index]);
            }
        }

        private Node splitNode(Node n, Entry newRect, int newId)
        {
            // [Pick first entry for each group] Apply algorithm pickSeeds to
            // choose two entries to be the first elements of the groups. Assign
            // each to a group.

            // debug code
            //float initialArea = 0;
            //if (log.IsDebugEnabled)
            //{
            //    Rectangle union = n.mbr.union(newRect);
            //    initialArea = union.area();
            //}

            System.Array.Copy(initialEntryStatus, 0, entryStatus, 0, maxNodeEntries);

            Node newNode = null;
            newNode = new Node(getNextNodeId(), n.level, maxNodeEntries);
            nodeMap.Add(newNode.nodeId, newNode);

            pickSeeds(n, newRect, newId, newNode); // this also sets the entryCount to 1

            // [Check if done] If all entries have been assigned, stop. If one
            // group has so few entries that all the rest must be assigned to it in
            // order for it to have the minimum number m, assign them and stop.
            while (n.entryCount + newNode.entryCount < maxNodeEntries + 1)
            {
                if (maxNodeEntries + 1 - newNode.entryCount == minNodeEntries)
                {
                    // assign all remaining entries to original node
                    for (int i = 0; i < maxNodeEntries; i++)
                    {
                        if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED)
                        {
                            entryStatus[i] = ENTRY_STATUS_ASSIGNED;
                            n.sumEntry.add(n.entries[i]);
                            n.entryCount++;
                        }
                    }
                    break;
                }
                if (maxNodeEntries + 1 - n.entryCount == minNodeEntries)
                {
                    // assign all remaining entries to new node
                    for (int i = 0; i < maxNodeEntries; i++)
                    {
                        if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED)
                        {
                            entryStatus[i] = ENTRY_STATUS_ASSIGNED;
                            newNode.addEntryNoCopy(n.entries[i], n.ids[i]);
                            n.entries[i] = null;
                        }
                    }
                    break;
                }

                // [Select entry to assign] Invoke algorithm pickNext to choose the
                // next entry to assign. Add it to the group whose covering rectangle
                // will have to be enlarged least to accommodate it. Resolve ties
                // by adding the entry to the group with smaller area, then to the
                // the one with fewer entries, then to either. Repeat from S2
                pickNext(n, newNode);
            }

            n.reorganize(this);

            // check that the MBR stored for each Node&lt;T&gt; is correct.
            if (INTERNAL_CONSISTENCY_CHECKING)
            {
                if (!n.sumEntry.Equals(calculateMBR(n)))
                {
                    System.Console.WriteLine("Error: splitNode old Node<T> MBR wrong");
                }

                if (!newNode.sumEntry.Equals(calculateMBR(newNode)))
                {
                    System.Console.WriteLine("Error: splitNode new Node<T> MBR wrong");
                }
            }

            // debug code
            //if (log.IsDebugEnabled)
            //{
            //    float newArea = n.mbr.area() + newNode.mbr.area();
            //    float percentageIncrease = (100 * (newArea - initialArea)) / initialArea;
            //    log.Debug("Node " + n.nodeId + " split. New area increased by " + percentageIncrease + "%");
            //}

            return newNode;
        }

        /// <summary>
        /// Pick the next entry to be assigned to a group during a Node&lt;T&gt; split.
        /// [Determine cost of putting each entry in each group] For each
        /// entry not yet in a group, calculate the area increase required
        /// in the covering rectangles of each group  
        /// </summary>
        /// <param name="n"></param>
        /// <param name="newNode"></param>
        /// <returns></returns>
        private int pickNext(Node n, Node newNode)
        {
            float maxDifference = float.NegativeInfinity;
            int next = 0;
            int nextGroup = 0;

            maxDifference = float.NegativeInfinity;

            //if (log.IsDebugEnabled)
            //{
            //    log.Debug("pickNext()");
            //}

            for (int i = 0; i < maxNodeEntries; i++)
            {
                if (entryStatus[i] == ENTRY_STATUS_UNASSIGNED)
                {

                    if (n.entries[i] == null)
                    {
                        System.Console.WriteLine("Error: Node<T> " + n.nodeId + ", entry " + i + " is null");
                    }

                    float nIncrease = n.sumEntry.MinDist(n.entries[i]);
                    float newNodeIncrease = newNode.sumEntry.MinDist(n.entries[i]);
                    float difference = Math.Abs(nIncrease - newNodeIncrease);

                    if (difference > maxDifference)
                    {
                        next = i;

                        if (nIncrease < newNodeIncrease)
                        {
                            nextGroup = 0;
                        }
                        else if (newNodeIncrease < nIncrease)
                        {
                            nextGroup = 1;
                        }
                        else if (n.sumEntry.area() < newNode.sumEntry.area())
                        {
                            nextGroup = 0;
                        }
                        else if (newNode.sumEntry.area() < n.sumEntry.area())
                        {
                            nextGroup = 1;
                        }
                        else if (newNode.entryCount < maxNodeEntries / 2)
                        {
                            nextGroup = 0;
                        }
                        else
                        {
                            nextGroup = 1;
                        }
                        maxDifference = difference;
                    }
                    //if (log.IsDebugEnabled)
                    //{
                    //    log.Debug("Entry " + i + " group0 increase = " + nIncrease + ", group1 increase = " + newNodeIncrease +
                    //              ", diff = " + difference + ", MaxDiff = " + maxDifference + " (entry " + next + ")");
                    //}
                }
            }

            entryStatus[next] = ENTRY_STATUS_ASSIGNED;

            if (nextGroup == 0)
            {
                n.sumEntry.add(n.entries[next]);
                n.entryCount++;
            }
            else
            {
                // move to new node.
                newNode.addEntryNoCopy(n.entries[next], n.ids[next]);
                n.entries[next] = null;
            }

            return next;
        }

        /// <summary>
        /// Pick the seeds used to split a node.
        /// Select two entries to be the first elements of the groups
        /// </summary>
        /// <param name="n"></param>
        /// <param name="newRect"></param>
        /// <param name="newId"></param>
        /// <param name="newNode"></param>
        private void pickSeeds(Node n, Entry newRect, int newId, Node newNode)
        {
            // Find extreme rectangles along all dimension. Along each dimension,
            // find the entry whose rectangle has the highest low side, and the one
            // with the lowest high side. Record the separation.
            float maxNormalizedSeparation = 0;
            int highestLowIndex = 0;
            int lowestHighIndex = 0;

            // for the purposes of picking seeds, take the MBR of the Node&lt;T&gt; to include
            // the new rectangle aswell.
            n.sumEntry.add(newRect);

            //if (log.IsDebugEnabled)
            //{
            //    log.Debug("pickSeeds(): NodeId = " + n.nodeId + ", newRect = " + newRect);
            //}

            for (int d = 0; d < newRect.getdimension(); d++)
            {
                float tempHighestLow = newRect.lowerBound[d];
                int tempHighestLowIndex = -1; // -1 indicates the new rectangle is the seed

                float tempLowestHigh = newRect.upperBound[d];
                int tempLowestHighIndex = -1;

                for (int i = 0; i < n.entryCount; i++)
                {
                    float tempLow = n.entries[i].lowerBound[d];
                    if (tempLow >= tempHighestLow)
                    {
                        tempHighestLow = tempLow;
                        tempHighestLowIndex = i;
                    }
                    else
                    {  // ensure that the same index cannot be both lowestHigh and highestLow
                        float tempHigh = n.entries[i].upperBound[d];
                        if (tempHigh <= tempLowestHigh)
                        {
                            tempLowestHigh = tempHigh;
                            tempLowestHighIndex = i;
                        }
                    }

                    // PS2 [Adjust for shape of the rectangle cluster] Normalize the separations
                    // by dividing by the widths of the entire set along the corresponding
                    // dimension
                    float normalizedSeparation = (tempHighestLow - tempLowestHigh) / (n.sumEntry.upperBound[d] - n.sumEntry.lowerBound[d]);

                    if (normalizedSeparation > 1 || normalizedSeparation < -1)
                    {
                        System.Console.WriteLine("Invalid normalized separation");
                    }

                    //if (log.IsDebugEnabled)
                    //{
                    //    log.Debug("Entry " + i + ", dimension " + d + ": HighestLow = " + tempHighestLow +
                    //              " (index " + tempHighestLowIndex + ")" + ", LowestHigh = " +
                    //              tempLowestHigh + " (index " + tempLowestHighIndex + ", NormalizedSeparation = " + normalizedSeparation);
                    //}

                    // PS3 [Select the most extreme pair] Choose the pair with the greatest
                    // normalized separation along any dimension.
                    if (normalizedSeparation > maxNormalizedSeparation)
                    {
                        maxNormalizedSeparation = normalizedSeparation;
                        highestLowIndex = tempHighestLowIndex;
                        lowestHighIndex = tempLowestHighIndex;
                    }
                }
            }

            // highestLowIndex is the seed for the new node.
            if (highestLowIndex == -1)
            {
                newNode.addEntry(newRect, newId);
            }
            else
            {
                newNode.addEntryNoCopy(n.entries[highestLowIndex], n.ids[highestLowIndex]);
                n.entries[highestLowIndex] = null;

                // move the new rectangle into the space vacated by the seed for the new node
                n.entries[highestLowIndex] = newRect;
                n.ids[highestLowIndex] = newId;
            }

            // lowestHighIndex is the seed for the original node.
            if (lowestHighIndex == -1)
            {
                lowestHighIndex = highestLowIndex;
            }

            entryStatus[lowestHighIndex] = ENTRY_STATUS_ASSIGNED;
            n.entryCount = 1;
            n.sumEntry.set(n.entries[lowestHighIndex].lowerBound, n.entries[lowestHighIndex].lowerBound);
        }

        #endregion

        #region DeleteEntry
        public bool DeleteEntry(Entry r, int id)
        {
            // FindLeaf algorithm inlined here. Note the "official" algorithm
            // searches all overlapping entries. This seems inefficient to me,
            // as an entry is only worth searching if it contains (NOT overlaps)
            // the rectangle we are searching for.
            //
            // Also the algorithm has been changed so that it is not recursive.

            // FL1 [Search subtrees] If root is not a leaf, check each entry
            // to determine if it contains r. For each entry found, invoke
            // findLeaf on the Node&lt;T&gt; pointed to by the entry, until r is found or
            // all entries have been checked.
            parents.Clear();
            parents.Push(rootNodeId);

            parentsEntry.Clear();
            parentsEntry.Push(-1);
            Node n = null;
            int foundIndex = -1;  // index of entry to be deleted in leaf

            while (foundIndex == -1 && parents.Count > 0)
            {
                n = getNode(parents.Peek());
                int startIndex = parentsEntry.Peek() + 1;

                if (!n.isLeaf())
                {
                    System.Console.WriteLine("searching Node<T> " + n.nodeId + ", from index " + startIndex);
                    //bool contains = false;
                    float leastEnlargement = n.getEntry(0).MinDist(r);
                    int index = 0; // index of rectangle in subtree
                    for (int i = startIndex; i < n.entryCount; i++)
                    {

                        Entry tempRectangle = n.getEntry(i);
                        float tempEnlargement = tempRectangle.MinDist(r);
                        if ((tempEnlargement < leastEnlargement) ||
                            ((tempEnlargement == leastEnlargement) &&
                             (tempRectangle.area() < n.getEntry(index).area())))
                        {
                            index = i;
                            leastEnlargement = tempEnlargement;
                        }

                        //// tinh toan lai contain theo mindist
                        //if (n.entries[i].contains(r))
                        //{
                           
                        //}
                    }
                    parents.Push(n.ids[index]);
                    parentsEntry.Pop();
                    parentsEntry.Push(index); // this becomes the start index when the child has been searched
                    parentsEntry.Push(-1);
                    //contains = true;

                    //if (contains)
                    //{
                    //    continue;
                    //}
                }
                else
                {
                    foundIndex = n.findEntry(r, id);
                }

                parents.Pop();
                parentsEntry.Pop();
            } // while not found

            if (foundIndex != -1)
            {
                n.deleteEntry(foundIndex, minNodeEntries);
                condenseTree(n);
                msize--;
            }

            // shrink the tree if possible (i.e. if root Node&lt;T%gt; has exactly one entry,and that
            // entry is not a leaf node, delete the root (it's entry becomes the new root)
            Node root = getNode(rootNodeId);
            while (root.entryCount == 1 && treeHeight > 1)
            {
                root.entryCount = 0;
                rootNodeId = root.ids[0];
                treeHeight--;
                root = getNode(rootNodeId);
            }

            return (foundIndex != -1);
        }

        private Entry oldEntry = new Entry();
        private void condenseTree(Node l)
        {
            // CT1 [Initialize] Set n=l. Set the list of eliminated
            // nodes to be empty.
            Node n = l;
            Node parent = null;
            int parentEntry = 0;

            //TIntStack eliminatedNodeIds = new TIntStack();
            Stack<int> eliminatedNodeIds = new Stack<int>();

            // CT2 [Find parent entry] If N is the root, go to CT6. Otherwise
            // let P be the parent of N, and let En be N's entry in P  
            while (n.level != treeHeight)
            {
                parent = getNode(parents.Pop());
                parentEntry = parentsEntry.Pop();

                // CT3 [Eliminiate under-full node] If N has too few entries,
                // delete En from P and add N to the list of eliminated nodes
                if (n.entryCount < minNodeEntries)
                {
                    parent.deleteEntry(parentEntry, minNodeEntries);
                    eliminatedNodeIds.Push(n.nodeId);
                }
                else
                {
                    // CT4 [Adjust covering rectangle] If N has not been eliminated,
                    // adjust EnI to tightly contain all entries in N
                    if (!n.sumEntry.Equals(parent.entries[parentEntry]))
                    {
                        oldEntry.set(parent.entries[parentEntry].lowerBound, parent.entries[parentEntry].upperBound);
                        parent.entries[parentEntry].set(n.sumEntry.lowerBound, n.sumEntry.upperBound);
                        parent.recalculateMBR(oldEntry);
                    }
                }
                // CT5 [Move up one level in tree] Set N=P and repeat from CT2
                n = parent;
            }

            // CT6 [Reinsert orphaned entries] Reinsert all entries of nodes in set Q.
            // Entries from eliminated leaf nodes are reinserted in tree leaves as in
            // Insert(), but entries from higher level nodes must be placed higher in
            // the tree, so that leaves of their dependent subtrees will be on the same
            // level as leaves of the main tree
            while (eliminatedNodeIds.Count > 0)
            {
                Node e = getNode(eliminatedNodeIds.Pop());
                for (int j = 0; j < e.entryCount; j++)
                {
                    InsertEntry(e.entries[j], e.ids[j], e.level);
                    e.entries[j] = null;
                }
                e.entryCount = 0;
                deletedNodeIds.Push(e.nodeId);
            }
        }

        #endregion

        #region Search
        public Entry Search(Entry p)
        {
            Entry retval = new Entry();
            Node rootNode = getNode(rootNodeId);
            float distance = rootNode.entries[0].MinDist(p);

            return Retreval(p, rootNode, distance);
        }

        public Entry Retreval(Entry p,Node T, float furthestDistance)
        {
            Entry retval = new Entry();
            float minDistance = furthestDistance;
            int index = 0;

            if (!T.isLeaf())
            {
                for (int i = 0; i < T.entryCount; i++)
                {
                    if (T.entries[i].MinDist(p) < minDistance)
                    {
                        index = i;
                        minDistance = T.entries[i].MinDist(p);
                    }
                    else if (T.entries[i].MinDist(p) == minDistance)
                    {
                        if (T.entries[i].area() <= T.entries[index].area())
                        {
                            index = i;
                            minDistance = T.entries[i].MinDist(p);
                        }
                    }
                }
                parents.Push(T.nodeId);
                parentsEntry.Push(index);

                // CL4 [Descend until a leaf is reached] Set N to be the child Node&lt;T&gt;
                // pointed to by Fp and repeat from CL2

                retval = Retreval(p, getNode(T.ids[index]), minDistance);
            }
            else
            {
                for (int i = 0; i < T.entryCount; i++)
                {
                    if (T.entries[i].MinDist(p) < minDistance)
                    {
                        index = i;
                        minDistance = T.entries[i].MinDist(p);
                    }
                    else if (T.entries[i].MinDist(p) == minDistance)
                    {
                        if (T.entries[i].area() <= T.entries[index].area())
                        {
                            index = i;
                            minDistance = T.entries[i].MinDist(p);
                        }
                    }
                }

                retval = T.entries[index];
            }

            return retval;
        }
       

        #endregion

        #region others
        /**
        * Get the next available Node&lt;T&gt; ID. Reuse deleted Node&lt;T&gt; IDs if
        * possible
        */
        private int getNextNodeId()
        {
            int nextNodeId = 0;
            if (deletedNodeIds.Count > 0)
            {
                nextNodeId = deletedNodeIds.Pop();
            }
            else
            {
                nextNodeId = 1 + highestUsedNodeId++;
            }
            return nextNodeId;
        }
        private Node getNode(int index)
        {
            return (Node)nodeMap[index];
        }

        private Entry calculateMBR(Node n)
        {
            Entry mbr = new Entry(n.entries[0].lowerBound, n.entries[0].upperBound);

            for (int i = 1; i < n.entryCount; i++)
            {
                mbr.add(n.entries[i]);
            }
            return mbr;
        }

        public int Count
        {
            get
            {
                return this.msize;
            }
        }
        #endregion
    

    }
}
